home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / flex / flexs237.zoo / ecs.c < prev    next >
C/C++ Source or Header  |  1990-06-28  |  9KB  |  350 lines
  1. /* ecs - equivalence class routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. #ifndef lint
  30. static char rcsid[] =
  31.     "@(#) $Header: /usr/fsys/odin/a/vern/flex/RCS/ecs.c,v 2.5 90/06/27 23:48:17 vern Exp $ (LBL)";
  32. #endif
  33.  
  34. #include "flexdef.h"
  35.  
  36. /* ccl2ecl - convert character classes to set of equivalence classes
  37.  *
  38.  * synopsis
  39.  *    ccl2ecl();
  40.  */
  41.  
  42. void ccl2ecl()
  43.  
  44.     {
  45.     int i, ich, newlen, cclp, ccls, cclmec;
  46.  
  47.     for ( i = 1; i <= lastccl; ++i )
  48.     {
  49.     /* we loop through each character class, and for each character
  50.      * in the class, add the character's equivalence class to the
  51.      * new "character" class we are creating.  Thus when we are all
  52.      * done, character classes will really consist of collections
  53.      * of equivalence classes
  54.      */
  55.  
  56.     newlen = 0;
  57.     cclp = cclmap[i];
  58.  
  59.     for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  60.         {
  61.         ich = ccltbl[cclp + ccls];
  62.         cclmec = ecgroup[ich];
  63.  
  64.         if ( xlation && cclmec < 0 )
  65.         {
  66.         /* special hack--if we're doing %t tables then it's
  67.          * possible that no representative of this character's
  68.          * equivalence class is in the ccl.  So waiting till
  69.          * we see the representative would be disastrous.  Instead,
  70.          * we add this character's equivalence class anyway, if it's
  71.          * not already present.
  72.          */
  73.         int j;
  74.  
  75.         /* this loop makes this whole process n^2; but we don't
  76.          * really care about %t performance anyway
  77.          */
  78.         for ( j = 0; j < newlen; ++j )
  79.             if ( ccltbl[cclp + j] == -cclmec )
  80.             break;
  81.  
  82.         if ( j >= newlen )
  83.             { /* no representative yet, add this one in */
  84.             ccltbl[cclp + newlen] = -cclmec;
  85.             ++newlen;
  86.             }
  87.         }
  88.  
  89.         else if ( cclmec > 0 )
  90.         {
  91.         ccltbl[cclp + newlen] = cclmec;
  92.         ++newlen;
  93.         }
  94.         }
  95.  
  96.     ccllen[i] = newlen;
  97.     }
  98.     }
  99.  
  100.  
  101. /* cre8ecs - associate equivalence class numbers with class members
  102.  *
  103.  * synopsis
  104.  *    int cre8ecs();
  105.  *    number of classes = cre8ecs( fwd, bck, num );
  106.  *
  107.  *  fwd is the forward linked-list of equivalence class members.  bck
  108.  *  is the backward linked-list, and num is the number of class members.
  109.  *
  110.  *  Returned is the number of classes.
  111.  */
  112.  
  113. int cre8ecs( fwd, bck, num )
  114. int fwd[], bck[], num;
  115.  
  116.     {
  117.     int i, j, numcl;
  118.  
  119.     numcl = 0;
  120.  
  121.     /* create equivalence class numbers.  From now on, abs( bck(x) )
  122.      * is the equivalence class number for object x.  If bck(x)
  123.      * is positive, then x is the representative of its equivalence
  124.      * class.
  125.      */
  126.     for ( i = 1; i <= num; ++i )
  127.     if ( bck[i] == NIL )
  128.         {
  129.         bck[i] = ++numcl;
  130.         for ( j = fwd[i]; j != NIL; j = fwd[j] )
  131.         bck[j] = -numcl;
  132.         }
  133.  
  134.     return ( numcl );
  135.     }
  136.  
  137.  
  138. /* ecs_from_xlation - associate equivalence class numbers using %t table
  139.  *
  140.  * synopsis
  141.  *    numecs = ecs_from_xlation( ecmap );
  142.  *
  143.  *  Upon return, ecmap will map each character code to its equivalence
  144.  *  class.  The mapping will be positive if the character is the representative
  145.  *  of its class, negative otherwise.
  146.  *
  147.  *  Returns the number of equivalence classes used.
  148.  */
  149.  
  150. int ecs_from_xlation( ecmap )
  151. int ecmap[];
  152.  
  153.     {
  154.     int i;
  155.     int nul_is_alone = false;
  156.     int did_default_xlation_class = false;
  157.  
  158.     if ( xlation[0] != 0 )
  159.     {
  160.     /* if NUL shares its translation with other characters, choose one
  161.      * of the other characters as the representative for the equivalence
  162.      * class.  This allows a cheap test later to see whether we can
  163.      * do away with NUL's equivalence class.
  164.      */
  165.     for ( i = 1; i < csize; ++i )
  166.         if ( xlation[i] == -xlation[0] )
  167.         {
  168.         xlation[i] = xlation[0];
  169.         ecmap[0] = -xlation[0];
  170.         break;
  171.         }
  172.  
  173.     if ( i >= csize )
  174.         /* didn't find a companion character--remember this fact */
  175.         nul_is_alone = true;
  176.     }
  177.  
  178.     for ( i = 1; i < csize; ++i )
  179.     if ( xlation[i] == 0 )
  180.         {
  181.         if ( did_default_xlation_class )
  182.         ecmap[i] = -num_xlations;
  183.         
  184.         else
  185.         {
  186.         /* make an equivalence class for those characters not
  187.          * specified in the %t table
  188.          */
  189.         ++num_xlations;
  190.         ecmap[i] = num_xlations;
  191.         did_default_xlation_class = true;
  192.         }
  193.         }
  194.  
  195.     else
  196.         ecmap[i] = xlation[i];
  197.  
  198.     if ( nul_is_alone )
  199.     /* force NUL's equivalence class to be the last one */
  200.     {
  201.     ++num_xlations;
  202.     ecmap[0] = num_xlations;
  203.  
  204.     /* there's actually a bug here: if someone is fanatic enough to
  205.      * put every character in its own translation class, then right
  206.      * now we just promoted NUL's equivalence class to be csize + 1;
  207.      * we can handle NUL's class number being == csize (by instead
  208.      * putting it in its own table), but we can't handle some *other*
  209.      * character having to be put in its own table, too.  So in
  210.      * this case we bail out.
  211.      */
  212.     if ( num_xlations > csize )
  213.         flexfatal( "too many %t classes!" );
  214.     }
  215.  
  216.     return num_xlations;
  217.     }
  218.  
  219.  
  220. /* mkeccl - update equivalence classes based on character class xtions
  221.  *
  222.  * synopsis
  223.  *    Char ccls[];
  224.  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
  225.  *    mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping );
  226.  *
  227.  * where ccls contains the elements of the character class, lenccl is the
  228.  * number of elements in the ccl, fwd is the forward link-list of equivalent
  229.  * characters, bck is the backward link-list, and llsiz size of the link-list
  230.  *
  231.  * NUL_mapping is the value which NUL (0) should be mapped to.
  232.  */
  233.  
  234. void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
  235. Char ccls[];
  236. int lenccl, fwd[], bck[], llsiz, NUL_mapping;
  237.  
  238.     {
  239.     int cclp, oldec, newec;
  240.     int cclm, i, j;
  241.     static unsigned char cclflags[CSIZE];    /* initialized to all '\0' */
  242.  
  243.     /* note that it doesn't matter whether or not the character class is
  244.      * negated.  The same results will be obtained in either case.
  245.      */
  246.  
  247.     cclp = 0;
  248.  
  249.     while ( cclp < lenccl )
  250.     {
  251.     cclm = ccls[cclp];
  252.  
  253.     if ( NUL_mapping && cclm == 0 )
  254.         cclm = NUL_mapping;
  255.  
  256.     oldec = bck[cclm];
  257.     newec = cclm;
  258.  
  259.     j = cclp + 1;
  260.  
  261.     for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  262.         { /* look for the symbol in the character class */
  263.         for ( ; j < lenccl; ++j )
  264.         {
  265.         register int ccl_char;
  266.  
  267.         if ( NUL_mapping && ccls[j] == 0 )
  268.             ccl_char = NUL_mapping;
  269.         else
  270.             ccl_char = ccls[j];
  271.  
  272.         if ( ccl_char > i )
  273.             break;
  274.  
  275.         if ( ccl_char == i && ! cclflags[j] )
  276.             {
  277.             /* we found an old companion of cclm in the ccl.
  278.              * link it into the new equivalence class and flag it as
  279.              * having been processed
  280.              */
  281.  
  282.             bck[i] = newec;
  283.             fwd[newec] = i;
  284.             newec = i;
  285.             cclflags[j] = 1;    /* set flag so we don't reprocess */
  286.  
  287.             /* get next equivalence class member */
  288.             /* continue 2 */
  289.             goto next_pt;
  290.             }
  291.         }
  292.  
  293.         /* symbol isn't in character class.  Put it in the old equivalence
  294.          * class
  295.          */
  296.  
  297.         bck[i] = oldec;
  298.  
  299.         if ( oldec != NIL )
  300.         fwd[oldec] = i;
  301.  
  302.         oldec = i;
  303. next_pt:
  304.         ;
  305.         }
  306.  
  307.     if ( bck[cclm] != NIL || oldec != bck[cclm] )
  308.         {
  309.         bck[cclm] = NIL;
  310.         fwd[oldec] = NIL;
  311.         }
  312.  
  313.     fwd[newec] = NIL;
  314.  
  315.     /* find next ccl member to process */
  316.  
  317.     for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
  318.         {
  319.         /* reset